import random


class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def insert(root, val):
    if not root:
        return Node(val)
    elif root.val > val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root


def qianxu(root):
    if not root:
        return
    qianxu(root.left)
    print(root.val)
    qianxu(root.right)


class Solution:
    def qianxu(self, root):
        if not root:
            return
        self.qianxu(root.left)
        self.a.append(root)
        self.qianxu(root.right)

    def treeToDoublyList(self, root: 'Node') -> 'Node':
        self.a = []
        self.qianxu(root)
        for i in range(len(self.a) - 1):
            self.a[i].right = self.a[i + 1]
            self.a[i + 1].left = self.a[i]
        self.a[-1].right = self.a[0]
        self.a[0].left=self.a[-1]


        head=self.a[0]
        return head


if __name__ == '__main__':
    a = list(range(10))
    random.shuffle(a)
    print(a)
    root = None
    for i in a:
        root = insert(root, i)

    s=Solution()
    s.treeToDoublyList(root)
